
/**
 * 冒泡排序
 * 思路：
 * 1.两两比较，大的往后排
 * 2.每次比较完，记录下最大的值，下次比较的时候，从第二位开始比较
 * 时间复杂度：O(n^2)
 * 空间复杂度：O(1)
 */


/**
 * 选择排序
 * 思路：从第一个开始，和后面的比较，如果比后面的大，则交换位置;经过一轮比较后，第一个元素应该是最小的
 * 时间复杂度：O(n^2)
 * 空间复杂度：O(1)
 */

/**
 * 插入排序
 * 思路：局部有序的思想，每次把一个元素插入到已排序的数组中，这样，数组就变成有序的了
 * 时间复杂度：O(n^2)
 * 空间复杂度：O(1)
 */

/**
 * 希尔排序
 * 思路：插入排序的一种更高效的实现，通过分组，减少比较次数，提高效率
 */

/**
 * 归并排序
 * 思路：分治思想，将数组分为两个子数组，然后对子数组进行排序，再合并
 */

/**
 * 快速排序
 * 思路：分治思想，将数组分为两个子数组，然后对子数组进行排序，再合并
 * 枢纽选取方法: 取index为头、中、位的三个数据排序后的中位数；如下图所示，按下标值取出的三个数据为：92，31，0，经排序后变为：0，31，92，取其中的中位数31作为枢纽（当（length-1）/2不整除时可向下或向上取整）：
 * 时间复杂度：O(nlogn)
 * 空间复杂度：O(logn)
 */
class Sort {
  constructor(arr) {
    this.arr = arr
  }
  // 交换数据的方法
  swap(i, j) {
    let temp = this.arr [i]
    this.arr[i] = this.arr[j]
    this.arr[j] = temp
  }
  // 获取快速排序的枢纽
  getMid() {
    let center = Math.floor((this.arr.length - 1) / 2),
      left = 0,
      right = this.arr.length - 1
      if (this.arr[center] < this.arr[left]) {
        this.swap(left, center)
      } 
      if (this.arr[center] > this.arr[right]) {
        this.swap(center,right)
      } 
      if (this.arr[left] > this.arr[right]) {
        this.swap(left, right)
      }
      return center
  }
  bubbleSort() {
    for (let i = 0; i < this.arr.length - 1; i ++) {
      for (let j = i + 1; j < this.arr.length; j ++) {
        if (this.arr[i] > this.arr[j]) {
          this.swap(i, j)
        }
      }
    }
    return this.arr
  }
  chooseSort() {
    for (let i = 0; i < this.arr.length - 1;i ++) {
      let min = i
      for (let j = i + 1; j < this.arr.length; j ++) {
        if (this.arr[min] > this.arr[j]) {
          min = j
        }
      }
      if (i !==  min) {
        this.swap(i, min)
      }
    }
    return this.arr
  }
  insertSort() {
    for (let i = 0; i < this.arr.length; i ++) {
      let j = i, temp = this.arr[i]
      while(this.arr[j - 1] > temp && j > 0) {
        // 大数据向右移动
        this.arr[j] = this.arr[j - 1]
        j-- 
      }
      this.arr[j] = temp
    }
    return this.arr
  }
  shellSort() {
    let gap = Math.floor(this.arr.length / 2)

    while (gap >= 1 ) {
      for (let i = gap; i < this.arr.length; i ++) {
        let j = i, temp = this.arr[i]

        while(this.arr[j - gap] > temp && j >= gap) {
          this.arr[j] = this.arr[j - gap]
          j -= gap
        }
        this.arr[j] = temp
      }
      gap = Math.floor(gap / 2)
    }
    return this.arr
  }
}

let sort = new Sort([-1, 1, 3, 2, 5, 4, 0, 5, -2])
// console.log('冒泡排序:>>> ', sort.bubbleSort())
// console.log('选择排序:>>> ', sort.chooseSort())
// console.log('插入排序:>>> ', sort.insertSort()) 
// console.log('希尔排序:>>> ', sort.shellSort())